\documentclass[12pt, a4paper]{article}
\usepackage{geometry}
\geometry{
	a4paper,
	left=12.7 mm,
	right=12.7 mm,
	top=12.7 mm,
	bottom=12.7 mm,
}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{physics}
\graphicspath{ {./} }
\usepackage{ctex}

\newcommand{\bvec}[1]{\mathbf{#1}}
\newcommand{\formula}[1]{\text{式} \ref{#1} }

\usepackage{booktabs}
\usepackage{multirow}
\usepackage{array}

\begin{document}
	\section{基本优化问题}
	\footnote{参考：Sauer 《数值分析》。本笔记使用AI辅助。}
	从完成数学作业、训练神经网络到在菜市场买菜，我们都离不开优化问题\textsl{（谁说买菜不需要数学？）}。
	优化问题是指找到某一个函数$f=f(x_1,x_2,...)$（在定义域上的）的极小值点。
	请注意这和找到函数零点的求根问题的相似与不同。
	
	以下简单介绍一些基本的优化方法。为了方便书写，我们以下定义$\bvec x = (x_1,x_2,...,)$。

	\subsection{梯度下降法}
	
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.3 \linewidth]{opt2}
		\caption{梯度下降示意图。背景：$f$等高线；蓝色线：局部(负)梯度场；红色线：梯度下降迭代过程}
		\label{fig:opt2}
	\end{figure}
	
	
	梯度下降法的思路非常简单直接：\textsl{往哪里走能使函数值下降最快，就往哪里走}。
	而学过高数的我们知道，在局部$\bvec x$处，函数变化最快的方向由函数该处的梯度给出：
	\begin{equation}
		\grad f |_{\bvec x} = 
		\left ( \pdv{f}{x_1}|_{\bvec x},\pdv{f}{x_2}|_{\bvec x},...\right)^T
	\end{equation}
	然而，梯度的方向是函数值上升最快的方向，因此加一个负号才是函数值下降最快的方向。
	因此，我们的梯度下降法可以写为：
	\begin{equation}
		\boxed
		{
			\begin{aligned}
				\Delta \bvec x = - \alpha (\grad f|_{\bvec x^{(k)}})\\
				\bvec x^{(k+1)} = \bvec x^{(k)} + \Delta \bvec x\\
			\end{aligned}
		}
	\end{equation}
	其中$\alpha$是一个参数，在深度学习的语境中被称为学习率。${(k)}$上标代表迭代步。

	梯度下降法是诸多优化方法的基础，例如神经网络训练中常用的Adam法是梯度下降法的一种变体。

	由于梯度下降法使用了函数的一阶导数，因此是一种一阶方法。在神经网络中，一阶导数可由自动微分机制从神经网络的结构中自动推知。

	\subsection{牛顿法}
	
	\textbf{一元函数}

	在寻找函数零点的求根问题中，我们已经知道寻找函数零点的牛顿方法，这相当于不断做函数的割线：
	\begin{equation}
		\text{寻找函数零点：} \qquad
		x^{(k+1)} = x^{(k)} - \frac{f(x^{(k)})}{f'(x^{(k)})}
	\end{equation}
	然而我们现在要找的是函数的极小值点，而非函数的零点。
	但是学过高数的我们又知道，函数的极小值点处函数的一阶导数$f'$等于$0$。
	因此，寻找$f$的极值点，相当于寻找$f'$的零点（虽然这不是很严谨，因为$f'=0$不一定意味此处是极值）：
	$$
	f \text{极小} \Rightarrow f'=0
	$$
	因此，我们得到了寻找函数极值的牛顿法：
	\begin{equation}
		\text{寻找函数极值点：} \qquad
		x^{(k+1)} = x^{(k)} - \frac{f'(x^{(k)})}{f''(x^{(k)})}
	\end{equation}
	
	\textbf{多元函数}

	多元函数的情况也类似，只不过函数的一阶导数被函数的梯度替代：
	\begin{equation}
		f' \Rightarrow \grad f = 
		\left ( \pdv{f}{x_1},\pdv{f}{x_2},...\right )^T
	\end{equation}
	而函数的二阶导数被Hessian矩阵替代：
	\begin{equation}
		f'' \Rightarrow H=
		\left (
		\begin{matrix}
			\pdv[2]{f}{x_1}{x_1} & \pdv[2]{f}{x_1}{x_2} & \dots \\
			\pdv[2]{f}{x_2}{x_1} & \pdv[2]{f}{x_2}{x_2} & \dots \\
			\pdv[2]{f}{x_3}{x_1} & \pdv[2]{f}{x_3}{x_2} & \dots \\
			\vdots & \vdots & \ddots \\
		\end{matrix}
		\right )
	\end{equation}
	由此我们得到了寻找多元函数极值的牛顿法：
	\begin{equation}
		\boxed
		{
			\begin{aligned}
				\Delta \bvec x = - H^{-1}(\grad f)\\
				\bvec x^{(k+1)} = \bvec x^{(k)} + \Delta \bvec x\\
			\end{aligned}
		}
	\end{equation}
	由于牛顿法使用了函数的二阶导数，因此它是一个二阶方法。在实际中函数的二阶导数不是那么容易获得，因此牛顿法的变体可能更常用。

	从以上的叙述中我们发现，这些优化方法并非“完美”，
	它不一定能收敛到全局最小值，而可能陷入局部极小值，乃至震荡发散等。
	这依赖于初始迭代点$\bvec x^{(0)}$的选取以及函数的性质等。
	这确实是一个难以解决的问题，并困扰着包括神经网络训练在内的无数优化问题。
	但是，有很多新的技术意图缓解这个问题。
\end{document}
